home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _maxflow.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  5.5 KB  |  238 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _maxflow.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #include <LEDA/graph_alg.h>
  19. #include <math.h>
  20.  
  21.  
  22. static void gt_bfs(node s_vert, int dist_s_vert, 
  23.                    const graph& G, node s, 
  24.                    const edge_array<num_type>& flow,
  25.                    const edge_array<num_type>& cap,
  26.                          node_data<int>& dist);
  27.  
  28.  
  29. num_type MAX_FLOW(graph& G, node s, node t, const edge_array<num_type>& cap, 
  30.                                                   edge_array<num_type>& flow)
  31. {
  32.  
  33. /* Computes a maximum flow from source s to sink t, using the
  34.    Goldberg-Tarjan algorithm [Journal ACM 35 (Oct 1988) p921-940].
  35.    ( Applies push steps to vertices with positive preflow, based on 
  36.      distance labels.  Uses FIFO rule (implemented by FIFO queue) 
  37.      for selecting a vertex with +ve preflow. )
  38.  
  39.    input:   cap[e]  gives capacity of edge e 
  40.  
  41.    output:  flow[e] flow on edge e
  42.             returns total flow into sink
  43.  
  44.    node_arrays used by the algorithm:
  45.    dist[v]   = lower bound on shortest distance from v to t
  46.    excess[v] = (total incoming preflow[v]) - (total outgoing preflow[v])
  47.  
  48.    Implemented by  Joseph Cheriyan & Stefan Naeher.
  49. */
  50.  
  51. node_data<int> dist(G,0);
  52.  
  53. node_array<num_type>  excess(G,0);
  54.  
  55. node_list U;   // FIFO Queue used for selecting vertex with positive preflow
  56. node v,w;
  57. edge e;
  58.  
  59. int N = G.number_of_nodes();
  60.  
  61. /*
  62.  heuristic: parameter for heuristic suggested by Goldberg to speed up algorithm 
  63.             compute exact distance labels after every "heuristic" relabel steps
  64.  
  65.             experiments indicate that sqrt(|E|) is a good choice  (S.N.)
  66. */
  67.  
  68. int heuristic = int(sqrt(G.number_of_edges()));
  69.  
  70. int limit_heur   = heuristic;
  71. int num_relabels = 0;
  72.  
  73. if (s == t) error_handler(1,"MAXFLOW: source == sink");
  74.  
  75. forall_edges(e,G) flow[e] = 0;
  76.  
  77. forall_out_edges(e,s) // saturate all edges leaving from s
  78. { v = target(e);
  79.   if (excess[v] == 0 && v!=s) U.append(v);
  80.   flow[e] = cap[e];
  81.   excess[v] += cap[e];
  82.  }
  83.  
  84. dist[s] = N;
  85.  
  86. while (! U.empty() )      /* main loop */
  87. { 
  88.   v = U.pop();
  89.  
  90.   if (v == t) continue;
  91.  
  92.   int dv = dist[v];
  93.  
  94.   num_type ev = excess[v];
  95.  
  96.   // push flow along each edge e = (v,w) in the residual graph with
  97.   // dist[v] == dist[w] + 1
  98.  
  99.   if (dv < N)
  100.    forall_out_edges(e,v)
  101.    { if (ev <= 0) break;
  102.      w = target(e);
  103.      if (dv == dist[w]+1)
  104.      { num_type delta = cap[e]-flow[e];
  105.        if (delta > 0)
  106.        { if (ev < delta) delta = ev;
  107.          if (excess[w] == 0) U.append(w);
  108.          flow[e] += delta;
  109.          excess[w] += delta;
  110.          ev -= delta;
  111.         }
  112.       }
  113.     }
  114.  
  115.   forall_in_edges(e,v)
  116.   { if (ev <= 0) break;
  117.     w = source(e);
  118.     if (dv == dist[w]+1)
  119.     { num_type delta = flow[e];
  120.       if (delta > 0)
  121.       { if (ev < delta) delta = ev;
  122.         if (excess[w] == 0 && w != s ) U.append(w);
  123.         flow[e] -= delta;
  124.         excess[w] += delta;
  125.         ev -= delta;
  126.        }
  127.      }
  128.  
  129.     } 
  130.  
  131.   excess[v] = ev;
  132.   
  133.   if (ev > 0)
  134.   {
  135.     // relabel vertex v (i.e. update dist[v]) because all
  136.     // admissible edges in the residual graph have been saturated 
  137.  
  138.     num_relabels++;
  139.   
  140.     if (heuristic && (num_relabels == limit_heur))
  141.       { 
  142.         // heuristic suggested by Goldberg to reduce number of relabels:
  143.         // periodically compute exact dist[] labels by two backward bfs 
  144.         // one starting at t and another starting at s
  145.  
  146.         limit_heur += heuristic;
  147.  
  148.        node x;
  149.        forall_nodes(x,G) dist[x] = MAXINT;
  150.  
  151.        gt_bfs(t,0,G,s,flow,cap,dist);
  152.        gt_bfs(s,N,G,s,flow,cap,dist);
  153.       }
  154.     else
  155.       { 
  156.         int min_dist = MAXINT;
  157.  
  158.         forall_out_edges(e,v)
  159.           if (cap[e] > flow[e] && dist[v] < N)
  160.             //pushes towards s that increase flow[e] are not allowed
  161.             min_dist = Min(min_dist,dist[target(e)]);
  162.  
  163.         forall_in_edges(e,v)
  164.           if (flow[e] > 0)
  165.             min_dist = Min(min_dist,dist[source(e)]);
  166.  
  167.         if (min_dist != MAXINT) min_dist++;
  168.         dist[v] = min_dist;
  169.        }
  170.  
  171.     if (! U.member(v) ) U.push(v);    
  172.      
  173.   } // if (excess[v] > 0)
  174.  
  175. }  // while (!U.empty())  
  176.        
  177.    
  178.  
  179. /*
  180. // code to verify that flow is legal
  181. num_type total_s_cap = 0;
  182. forall_out_edges(e,s)  total_s_cap += cap[e];
  183. if (total_s_cap != (excess[s] + excess[t]))
  184.    error_handler(999,"gt_max_flow: total out cap s != excess[s] + excess[t]");
  185. */
  186.  
  187. return excess[t];  // value of maximum flow from s to t
  188.   
  189. }
  190.  
  191.  
  192.  
  193.  
  194. //procedure to perform backward bfs starting at vertex s_vert with 
  195. //distance label dist_s_vert
  196.  
  197. static
  198. void gt_bfs(node s_vert, 
  199.             int dist_s_vert, 
  200.             const graph& G, 
  201.             node s, 
  202.             const edge_array<num_type>& flow,
  203.             const edge_array<num_type>& cap, 
  204.             node_data<int>& dist)
  205. { 
  206.   node_queue Q;
  207.  
  208.   Q.append(s_vert);
  209.   dist[s_vert] = dist_s_vert;
  210.  
  211.   while (! Q.empty() )
  212.   { 
  213.     node x = Q.pop();
  214.     int  d = dist[x] + 1;
  215.  
  216.     edge e;
  217.     forall_out_edges(e,x)
  218.     { node y = target(e); 
  219.       if (flow[e] > 0 && dist[y] == MAXINT) // use only edges with positive flow
  220.       { dist[y] = d;
  221.         Q.append(y);
  222.         if (y == s) dist[y] = G.number_of_nodes();
  223.        }
  224.      }
  225.  
  226.     forall_in_edges(e,x)
  227.     { node y = source(e); 
  228.       if (cap[e] > flow[e] && dist[y] == MAXINT &&  s_vert != s)
  229.       { dist[y] = d;
  230.         Q.append(y);
  231.         if (y == s) dist[y] = G.number_of_nodes();
  232.        }
  233.      }
  234.  
  235.    } // while Q not empty
  236. }
  237.  
  238.